package com.hdu.other.binarySearch;

import java.util.PriorityQueue;

public class lc875 {

    class Solution {
        public int minRefuelStops(int target, int startFuel, int[][] stations) {
            if (startFuel >= target) return 0;
            int cur = startFuel;
            int ans = 0;
            PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
                return b - a;
            });
            for(int i = 0; i < stations.length; i++) {
                int[] curStation = stations[i];
                int pos = curStation[0];
                int fuel = curStation[1];
                if (cur < pos)
                {
                    while (cur < pos && !pq.isEmpty())
                    {
                        cur += pq.poll();
                        ans++;
                    }
                    if (cur < pos)
                        return -1;
                    if (cur >= target)
                        return ans;
                }
                pq.offer(fuel);
            }

            while (cur < target && !pq.isEmpty())
            {
                cur += pq.poll();
                ans++;
                if (cur >= target) return ans;
            }
            return ans;
        }
    }
}
